package com.maishi.programmer.jainzhioffer;

import java.util.ArrayList;
import java.util.TreeSet;

/**
 * Created by brossdong on 2018/4/4.
 * 输入一个字符串,按字典序打印出该字符串中字符的所有排列。
 * 例如输入字符串abc,
 * 则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
 */
public class TestProblem38 {

    public static ArrayList<String> Permutation (String str) {

        ArrayList<String> result = new ArrayList<>();
        if (str.length() <= 0 || str == null) return result;

        char[] chars = str.toCharArray();
        //用于排序输出
        TreeSet<String> res = new TreeSet<>();
        getResult(chars,0,str.length()-1,res);
        result.addAll(res) ;//添加到ArrayList
        return result ;
    }

    public static void getResult (char[] chars,int start,int end,TreeSet<String> res) {
        if (start == end) {
            res.add(String.valueOf(chars));
        } else {
            for (int i = start;i <= end;i++) {
                //换一位
                swap(chars,start,i);
                //递归
                getResult(chars,start+1,end,res);
                //换回来,保证下次换位正确性
                swap(chars,start,i);
            }
        }
    }

    public static void swap (char[] chars,int a,int b) {
        if (a == b) {

        } else {
            char temp = chars[a];
            chars[a] = chars[b];
            chars[b] = temp;
        }
    }



    public static void main(String[] args) {
        ArrayList<String> abc = Permutation("abcd");
        System.out.println(abc);
    }

}
